package com.leetcode.dynamic_programming;

/**
 * @author Dennis Li
 * @date 2020/8/12 21:20
 */
public class NthUglyNumber_264 {

    // 三指针法 -- 与动态规划进行结合
    // 尝试！尝试！尝试！ -- 先尝试，在尝试的基础上进行判断
    public int nthUglyNumber(int n) {
        final int[] dp = new int[n];
        dp[0] = 1;
        // 准备三个指针，分别指向 2 3 5 的三个指数位
        // 通过尝试移动3个指针的位置，得到下一个数，根据下一个数的结果再来求值
        int p2, p3, p5;
        p2 = p3 = p5 = 0;
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(dp[p2] * 2, Math.min(dp[p3] * 3, dp[p5] * 5));
            // 根据结果 移动丑数指针
            if (dp[i] == dp[p2] * 2) p2++;
            if (dp[i] == dp[p3] * 3) p3++;
            if (dp[i] == dp[p5] * 5) p5++;
        }
        return dp[n - 1];
    }

}
